珂朵莉树学习笔记

0XFF 珂朵莉美图欣赏

珂朵莉太可爱啦!\text{\Huge 珂朵莉太可爱啦!}

警告:前方高能\text{\Huge\color{red}{警告:前方高能}}

中国珂学院

行了别看了赶紧进入正题

0X00 简介

设计一个数据结构,区间加?

简单,线段树!

求区间第k小值?

主席树板子题!

区间推平赋值?还要查询区间k次幂的和?

……

不知道怎么办了吧!这四个操作是珂朵莉树最经典的操作。下面让我们跟着题目往下看。

0X01 模板题 - 基本操作

总结一下上面说的操作:区间加、区间赋值、查询区间第k小、查询区间幂次和。

下面看一道模板题:传送门

不要一看是黑题就害怕,珂朵莉树的本质其实就是拿一个set瞎暴力!

0X01-1 结构体定义

typedef long long ll;
struct Node
{
    ll l, r;
    mutable ll v;
    Node(ll x, ll y=-1, ll z=0) : l(x), r(y), v(z) {}
    bool operator < (const Node &a) const {return l < a.l;}
}
set<Node> ODT;
typedef set<Node>::iterator IT;

l、r表示区间左右端点,v是区间权值。下面那行定义了一个构造函数,方便以后使用。最后重载了小于运算符,按照区间左端点顺序排序,因为后面用的时候区间不存在重叠,所以其实就是让区间依次排序。

0X01-2 split

split操作用于将整段在pos的位置拆分为两小段,方便后续操作。

IT split(ll pos)
{
	IT iter = ODT.lower_bound(Node(pos));
	if(iter != ODT.end() && iter->l == pos) return iter;//不需要拆分
	--iter;//一定在前一区间内
	ll L = iter->l, R = iter->r, V = iter->v;//把值取出
	ODT.erase(iter);//删除待拆分的原区间
	ODT.insert(Node(L, pos-1, V));//插入新区间,Node(L, pos-1, V)利用构造函数生成Node类
	return ODT.insert(Node(pos, R, V)).first;//插入新区间并返回目标位置
}

0X01-3 区间加

区间加法其实就是把要加的段取出来暴力加。注意这里必须先split右边再split左边!

void update(ll l, ll r, ll dt)
{
	IT iterR = split(r+1), iterL = split(l);//必须先split右边再split左边
	for(iterL;iterL!=iterR;++iterL) iterL->v += dt;//暴力加整个区间
}

0X01-4 区间赋值

区间赋值也是取出要用的区间,把所有范围内的区间删掉,然后重新插入一个新区间。

void assign_val(ll l, ll r, ll w)
{
	IT iterR = split(r+1), iterL = split(l);
	ODT.erase(iterL, iterR);//删除赋值范围内所有区间
	ODT.insert(Node(l, r, w));//添加被删除的区间,权值直接改成要赋的值
}

0X01-5 求区间内排名为k的数

就是求区间第k小,把区间所有数压进vector,然后排序即可。

ll ranking(ll l, ll r, ll k)
{
	vector<pair<ll, ll> > v;//声明vector,pair->first是值,pair->second是个数
	IT iterR = split(r+1), iterL = split(l);
	for(iterL;iterL!=iterR;++iterL) v.push_back(make_pair(iterL->v, iterL->r-iterL->l+1));//把区间内所有数push进vector
	sort(v.begin(), v.end());//vector排序
	for(vector<pair<ll, ll> >::iterator iter=v.begin();iter!=v.end();++iter)
	{
		k -= iter->second;
		if(k <= 0) return iter->first;//不断降低k,直到k<=0,输出
	}
}

0X01-6 求区间所有数乘k次幂的和

区间幂次和,暴力算出所有的幂次和,加起来即可,这里需要使用快速幂。

ll qpow(ll x, ll y, ll MOD)//快速幂,相信你们都会,不用解释了
{
	ll ret = 1;
	ll ans = x % MOD;
	while(y)
	{
		if(y&1) ret = ret * ans % MOD;
		ans = ans * ans % MOD;
		y >>= 1;
	}
	return ret;
}

ll sum(ll l, ll r, ll x, ll y)//区间幂次和
{
	ll ans = 0;
	IT iterR = split(r+1), iterL = split(l);
	for(iterL;iterL!=iterR;++iterL)//枚举所有区间,算出幂次和
		ans = (ans + (iterL->r - iterL->l + 1) * qpow(iterL->v, x, y)) % y;
	return ans;
}

0X01-7 完整程序

下面就是完整程序了。怎么样?是不是感觉很暴力很容易理解?

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007LL;
const ll MAXN = 100001;

ll n, m, seed, vmax;
ll a[MAXN];
struct Node
{
	ll l, r;
	mutable ll v;
	Node(ll x, ll y = -1, ll z = 0): l(x), r(y), v(z) {}
	bool operator < (const Node &a) const {return l < a.l;}
};
typedef set<Node>::iterator IT;
set<Node> ODT;

ll rnd() //题目中要求的随机函数
{
	ll ret = seed;
	seed = (seed * 7 + 13) % mod;
	return ret;
}

IT split(ll pos)
{
	IT iter = ODT.lower_bound(Node(pos));
	if(iter != ODT.end() && iter->l == pos) return iter;
	--iter;
	ll L = iter->l, R = iter->r, V = iter->v;
	ODT.erase(iter);
	ODT.insert(Node(L, pos-1, V));
	return ODT.insert(Node(pos, R, V)).first;
}

void update(ll l, ll r, ll dt)
{
	IT iterR = split(r+1), iterL = split(l);
	for(iterL;iterL!=iterR;++iterL) iterL->v += dt;
}

void assign_val(ll l, ll r, ll w)
{
	IT iterR = split(r+1), iterL = split(l);
	ODT.erase(iterL, iterR);
	ODT.insert(Node(l, r, w));
}

ll ranking(ll l, ll r, ll k)
{
	vector<pair<ll, ll> > v;
	IT iterR = split(r+1), iterL = split(l);
	for(iterL;iterL!=iterR;++iterL) v.push_back(make_pair(iterL->v, iterL->r-iterL->l+1));
	sort(v.begin(), v.end());
	for(vector<pair<ll, ll> >::iterator iter=v.begin();iter!=v.end();++iter)
	{
		k -= iter->second;
		if(k <= 0) return iter->first;
	}
}

ll qpow(ll x, ll y, ll MOD)
{
	ll ret = 1;
	ll ans = x % MOD;
	while(y)
	{
		if(y&1) ret = ret * ans % MOD;
		ans = ans * ans % MOD;
		y >>= 1;
	}
	return ret;
}

ll sum(ll l, ll r, ll x, ll y)
{
	ll ans = 0;
	IT iterR = split(r+1), iterL = split(l);
	for(iterL;iterL!=iterR;++iterL)
		ans = (ans + (iterL->r - iterL->l + 1) * qpow(iterL->v, x, y)) % y;
	return ans;
}

int main()
{
	scanf("%lld%lld%lld%lld", &n, &m, &seed, &vmax);
	for(ll i=1;i<=n;i++)
	{
		a[i] = (rnd() % vmax) + 1;
		ODT.insert(Node(i, i, a[i]));
	}
	for(ll i=1;i<=m;i++)
	{
		ll op = rnd() % 4 + 1;
		ll l = rnd() % n + 1;
		ll r = rnd() % n + 1;
		if(l > r) swap(l, r);
		ll x, y;
		if(op == 3) x = rnd() % (r - l + 1) + 1;
		else x = rnd() % vmax + 1;
		if(op == 4) y = rnd() % vmax + 1;
		if(op == 1) update(l, r, x);
		else if(op == 2) assign_val(l, r, x);
		else if(op == 3) printf("%lld\n", ranking(l, r, x));
		else printf("%lld\n", sum(l, r, x, y));
	}
	return 0;
}

0X02 其他题目

看这个题单,另外P2894可以通过珂朵莉树拿到92分(别问我怎么知道的)。